// 力扣427. 建立四叉树
class Node {
    public boolean val;
    public boolean isLeaf;
    public Node topLeft;
    public Node topRight;
    public Node bottomLeft;
    public Node bottomRight;

    
    public Node() {
        this.val = false;
        this.isLeaf = false;
        this.topLeft = null;
        this.topRight = null;
        this.bottomLeft = null;
        this.bottomRight = null;
    }
    
    public Node(boolean val, boolean isLeaf) {
        this.val = val;
        this.isLeaf = isLeaf;
        this.topLeft = null;
        this.topRight = null;
        this.bottomLeft = null;
        this.bottomRight = null;
    }
    
    public Node(boolean val, boolean isLeaf, Node topLeft, Node topRight, Node bottomLeft, Node bottomRight) {
        this.val = val;
        this.isLeaf = isLeaf;
        this.topLeft = topLeft;
        this.topRight = topRight;
        this.bottomLeft = bottomLeft;
        this.bottomRight = bottomRight;
    }
}

class Solution {
    public Node construct(int[][] grid) {
        return buildQuadTree(grid, 0, 0, grid.length);
    }

    private Node buildQuadTree(int[][] grid, int x, int y, int size) {
        // 基本情况：当前区域大小为1，直接创建叶子节点
        if (size == 1) {
            return new Node(grid[x][y] == 1, true);
        }

        // 检查当前区域是否所有值相同
        boolean allSame = true;
        int firstVal = grid[x][y];
        outer:
        for (int i = x; i < x + size; i++) {
            for (int j = y; j < y + size; j++) {
                if (grid[i][j] != firstVal) {
                    allSame = false;
                    break outer;
                }
            }
        }

        // 如果所有值相同，创建叶子节点
        if (allSame) {
            return new Node(firstVal == 1, true);
        }

        // 否则分割为四个子区域并递归构建
        int newSize = size / 2;
        Node topLeft = buildQuadTree(grid, x, y, newSize);
        Node topRight = buildQuadTree(grid, x, y + newSize, newSize);
        Node bottomLeft = buildQuadTree(grid, x + newSize, y, newSize);
        Node bottomRight = buildQuadTree(grid, x + newSize, y + newSize, newSize);

        return new Node(false, false, topLeft, topRight, bottomLeft, bottomRight);
        // 都可以, 值是true或者false都可以
        // return new Node(true, false, topLeft, topRight, bottomLeft, bottomRight);
    }
}